package com.example.designpatterns.iterator.advanced;

import com.example.designpatterns.iterator.Iterator;
import java.util.Stack;

/**
 * 前序遍历迭代器
 * 遍历顺序：根节点 -> 左子树 -> 右子树
 * @param <T> 元素类型
 */
public class PreOrderIterator<T extends Comparable<T>> implements Iterator<T> {
    private Stack<TreeCollection.TreeNode<T>> stack;
    
    /**
     * 创建前序遍历迭代器
     * @param treeCollection 二叉树集合
     */
    public PreOrderIterator(TreeCollection<T> treeCollection) {
        this.stack = new Stack<>();
        TreeCollection.TreeNode<T> root = treeCollection.getRoot();
        if (root != null) {
            stack.push(root);
        }
    }
    
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    @Override
    public T next() {
        if (!hasNext()) {
            return null;
        }
        
        // 取出当前节点
        TreeCollection.TreeNode<T> node = stack.pop();
        T result = node.value;
        
        // 先放入右子节点，再放入左子节点（因为栈是后进先出）
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
        
        return result;
    }
} 